package leetcode.动态规划和贪心;

import java.util.Arrays;
/*
分析：偷窃 [0....n-1] 这些房子里面的财物，一共 n 个房子
假设第一次偷窃的是 0 号，下一次应该偷窃 [2....n-1] 里面的任意一个
若第二次偷窃的是 5 号，下一次应该偷窃 [7....n-1] 里面的任意一个
                              [0....n-1]
                           /     |  ..   \
                          0      2      n-1
                          |
                     [2....n-1]
                     /  ...  \
                    2       n-1
发现出现了很多重叠子问题
于是想到使用动态规划求解
所以，需要寻找状态转移方程，
现在假设 f(n) 表示从第 n 个房子开始偷，最后的受益最大，则：
f(0) = max{ v(0)+f(2)，v(1)+f(3), ... , v(n-3)+f(n-1), v(n-2), v(n-1) }

 */
public class Test198打家劫舍 {

    // 循环求解，状态转移方程：dp[i] = max(dp[i], nums[j] + dp[j+2])
    public static int rob(int[] nums) {
        int n = nums.length;
        if (n == 0)
            return 0;
        int[] dp = new int[n];
        // 自底向上的话，最基本的节就是 n-1 的值 (数组里面没有索引 n)
        // 偷取最后一个房子的财物，结果就是 n-1 的值
        dp[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            // 从 dp[i.....n-1] 开始偷取
            // 使用 dp 保存会重复出现的结果
            for (int j = i; j < n; j++) {
                dp[i] = Math.max(dp[i], nums[j] + (j + 2 < n ? dp[j + 2] : 0)); // 注意这里是加法，计算总盗窃值
                // 这里为什么是 dp[j+2],而不是nums[j+2]，因为j+2一定是被计算过了的，既然
                // 已经被计算了，一定存储在 dp 中，直接取出即可
                // 若 j+2 越界了，说明计算还刚刚开始，返回 0 即可
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        System.out.println(rob2(new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}));
    }

    /**
     * 递归解法：递归涉及到重叠子问题，需要存储一下已经计算过的值
     * 状态转移方程：dp[i] = max{ dp[i], nums[j] + dp[j+2]) }
     */
    static int[] dp;

    public static int rob2(int[] nums) {
        dp = new int[nums.length];
        Arrays.fill(dp, -1);
        // 从第一个房子开始偷
        return f(nums, 0);
    }
    /**
     *
     * @param nums 待抢劫的房子以及它里面的价值
     * @param index 抢劫的房子编号
     * @return 最大价值
     */
    public static int f(int[] nums, int index) {
        // 递归结束的条件
        if (index >= nums.length)
            return 0;
        // 子问题不用再次求解了
        if (dp[index] != -1)
            return dp[index];
        int res = 0;
        // 按照状态方程，从第 N 个房子开始偷取
        for (int i = index; i < nums.length; i++) {
            /*
            nums[i] + f(nums, i + 2) 表示先偷取第 i 个房子，
            然后从 i+2 开始递归处理

            取结果最大的值
             */
            res = Math.max(res, nums[i] + f(nums, i + 2));
        }
        dp[index] = res;
        return res;
    }

}
